package 剑指专题.搜索算法;


/*
 * Author：江松
 * Date：2023/3/29 12:29
 *
 法1：通过找到两端的小数，来得出范围大小
 法2：分别计算左右边界，
 如果没找到那么left就是数组中最接近这个数的左边
 right就是最接近这个数的右边
 */

public class Main1 {

    public  int left_bound(int a[], int key) {
        int l = 0, r = a.length - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);//防止死循环
            if (a[mid] < key) {
                l = mid + 1;
            } else if (a[mid] > key) {
                r = mid - 1;
            } else  {//如果只需要找到该值，就可以暂停或返回了
                r = mid - 1;//继续向左找(区间向左缩小)
            }
        }
        return l;
    }

    public  int right_bound(int a[], int key) {
        int l = 0, r = a.length - 1;
        while (l <= r) {
            int mid = ((r - l) >> 1)+l ;
            if (a[mid] < key) {
                l = mid + 1;
            } else if (a[mid] > key) {
                r = mid - 1;
            } else {
                l = mid + 1;//往右找(区间向右增大)
            }
        }
        return r;
    }
    public int bs(int []a,double k){
        int l=0,r=a.length-1;
        while(l<=r){
            int mid=l+r>>1;
            if(a[mid]<k){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return l;
    }
    public int GetNumberOfK(int [] array , int k) {
        if(array.length==0)return 0;
        return bs(array,k+0.5)-bs(array,k-0.5);
    }
}
